Mi manual de algoritmos/version_maraton_interuniversitaria_2008-2/src/grafos/bellman.tex

   1 % Generator: GNU source-highlight, by Lorenzo Bettini, http://www.gnu.org/software/src-highlite
   2
   3 {\ttfamily \raggedright {
   4 \noindent
   5 \mbox{}\textbf{\textcolor{Blue}{struct}}\ edge\textcolor{Red}{\{} \\
   6 \mbox{}\ \ \textcolor{ForestGreen}{int}\ u\textcolor{BrickRed}{,}\ v\textcolor{BrickRed}{,}\ w\textcolor{BrickRed}{;} \\
   7 \mbox{}\textcolor{Red}{\}}\textcolor{BrickRed}{;} \\
   8 \mbox{} \\
   9 \mbox{}edge\ \textcolor{BrickRed}{*}\ e\textcolor{BrickRed}{;}\ \textit{\textcolor{Brown}{//e\ =\ Arreglo\ de\ todas\ las\ aristas}} \\
  10 \mbox{}\textcolor{ForestGreen}{long}\ \textcolor{ForestGreen}{long}\ d\textcolor{BrickRed}{[}\textcolor{Purple}{300}\textcolor{BrickRed}{];}\ \textit{\textcolor{Brown}{//Distancias}} \\
  11 \mbox{}\textcolor{ForestGreen}{int}\ n\textcolor{BrickRed}{;}\ \textit{\textcolor{Brown}{//Cantidad\ de\ nodos}} \\
  12 \mbox{}\textcolor{ForestGreen}{int}\ m\textcolor{BrickRed}{;}\ \textit{\textcolor{Brown}{//Cantidad\ de\ aristas}} \\
  13 \mbox{} \\
  14 \mbox{}\textit{\textcolor{Brown}{/*}} \\
  15 \mbox{}\textit{\textcolor{Brown}{\ \ Retorna\ falso\ si\ hay\ un\ ciclo\ de\ costo\ negativo.}} \\
  16 \mbox{} \\
  17 \mbox{}\textit{\textcolor{Brown}{\ \ Si\ retorna\ verdadero,\ entonces\ d[i]\ contiene\ la\ distancia\ más\ corta\ entre\ el\ s\ y\ el\ nodo\ i.}} \\
  18 \mbox{}\textit{\textcolor{Brown}{\ */}} \\
  19 \mbox{}\textcolor{ForestGreen}{bool}\ \textbf{\textcolor{Black}{bellman}}\textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ \textcolor{BrickRed}{\&}s\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  20 \mbox{}\ \ \textit{\textcolor{Brown}{//Llenar\ e}} \\
  21 \mbox{}\ \ e\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Blue}{new}}\ edge\textcolor{BrickRed}{[}n\textcolor{BrickRed}{];} \\
  22 \mbox{}\ \ \textit{\textcolor{Brown}{//...}} \\
  23 \mbox{} \\
  24 \mbox{}\ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}n\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\ d\textcolor{BrickRed}{[}i\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ INT$\_$MAX\textcolor{BrickRed}{;} \\
  25 \mbox{}\ \ d\textcolor{BrickRed}{[}s\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ 0LL\textcolor{BrickRed}{;} \\
  26 \mbox{} \\
  27 \mbox{}\ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ i\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ i\textcolor{BrickRed}{$<$}n\textcolor{BrickRed}{-}\textcolor{Purple}{1}\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}i\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  28 \mbox{}\ \ \ \ \textcolor{ForestGreen}{bool}\ cambio\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Blue}{false}}\textcolor{BrickRed}{;} \\
  29 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ j\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ j\textcolor{BrickRed}{$<$}m\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}j\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  30 \mbox{}\ \ \ \ \ \ \textcolor{ForestGreen}{int}\ u\ \textcolor{BrickRed}{=}\ e\textcolor{BrickRed}{[}j\textcolor{BrickRed}{].}u\textcolor{BrickRed}{,}\ v\ \textcolor{BrickRed}{=}\ e\textcolor{BrickRed}{[}j\textcolor{BrickRed}{].}v\textcolor{BrickRed}{;} \\
  31 \mbox{}\ \ \ \ \ \ \textcolor{ForestGreen}{long}\ \textcolor{ForestGreen}{long}\ w\ \textcolor{BrickRed}{=}\ e\textcolor{BrickRed}{[}j\textcolor{BrickRed}{].}w\textcolor{BrickRed}{;} \\
  32 \mbox{}\ \ \ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}d\textcolor{BrickRed}{[}u\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{+}\ w\ \textcolor{BrickRed}{$<$}\ d\textcolor{BrickRed}{[}v\textcolor{BrickRed}{])}\textcolor{Red}{\{} \\
  33 \mbox{}\ \ \ \ \ \ \ \ d\textcolor{BrickRed}{[}v\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{=}\ d\textcolor{BrickRed}{[}u\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{+}\ w\textcolor{BrickRed}{;} \\
  34 \mbox{}\ \ \ \ \ \ \ \ cambio\ \textcolor{BrickRed}{=}\ \textbf{\textcolor{Blue}{true}}\textcolor{BrickRed}{;} \\
  35 \mbox{}\ \ \ \ \ \ \textcolor{Red}{\}} \\
  36 \mbox{}\ \ \ \ \textcolor{Red}{\}} \\
  37 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(!}cambio\textcolor{BrickRed}{)}\ \textbf{\textcolor{Blue}{break}}\textcolor{BrickRed}{;}\ \textit{\textcolor{Brown}{//Early-exit}} \\
  38 \mbox{}\ \ \textcolor{Red}{\}} \\
  39 \mbox{} \\
  40 \mbox{}\ \ \textbf{\textcolor{Blue}{for}}\ \textcolor{BrickRed}{(}\textcolor{ForestGreen}{int}\ j\textcolor{BrickRed}{=}\textcolor{Purple}{0}\textcolor{BrickRed}{;}\ j\textcolor{BrickRed}{$<$}m\textcolor{BrickRed}{;}\ \textcolor{BrickRed}{++}j\textcolor{BrickRed}{)}\textcolor{Red}{\{} \\
  41 \mbox{}\ \ \ \ \textcolor{ForestGreen}{int}\ u\ \textcolor{BrickRed}{=}\ e\textcolor{BrickRed}{[}j\textcolor{BrickRed}{].}u\textcolor{BrickRed}{,}\ v\ \textcolor{BrickRed}{=}\ e\textcolor{BrickRed}{[}j\textcolor{BrickRed}{].}v\textcolor{BrickRed}{;} \\
  42 \mbox{}\ \ \ \ \textcolor{ForestGreen}{long}\ \textcolor{ForestGreen}{long}\ w\ \textcolor{BrickRed}{=}\ e\textcolor{BrickRed}{[}j\textcolor{BrickRed}{].}w\textcolor{BrickRed}{;} \\
  43 \mbox{}\ \ \ \ \textbf{\textcolor{Blue}{if}}\ \textcolor{BrickRed}{(}d\textcolor{BrickRed}{[}u\textcolor{BrickRed}{]}\ \textcolor{BrickRed}{+}\ w\ \textcolor{BrickRed}{$<$}\ d\textcolor{BrickRed}{[}v\textcolor{BrickRed}{])}\ \textbf{\textcolor{Blue}{return}}\ \textbf{\textcolor{Blue}{false}}\textcolor{BrickRed}{;} \\
  44 \mbox{}\ \ \textcolor{Red}{\}} \\
  45 \mbox{} \\
  46 \mbox{}\ \ \textbf{\textcolor{Blue}{delete}}\ \textcolor{BrickRed}{[]}\ e\textcolor{BrickRed}{;} \\
  47 \mbox{}\ \ \textbf{\textcolor{Blue}{return}}\ \textbf{\textcolor{Blue}{true}}\textcolor{BrickRed}{;} \\
  48 \mbox{}\textcolor{Red}{\}} \\
  49
  50 } \normalfont\normalsize